{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Matrix Cells in Distance Order"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #geometry #array #math #matrix #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #几何 #数组 #数学 #矩阵 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: allCellsDistOrder"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #距离顺序排列矩阵单元格"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定四个整数 <code>rows</code>&nbsp;,&nbsp; &nbsp;<code>cols</code> ,&nbsp; <code>rCenter</code> 和 <code>cCenter</code> 。有一个&nbsp;<code>rows x cols</code>&nbsp;的矩阵，你在单元格上的坐标是&nbsp;<code>(rCenter, cCenter)</code> 。</p>\n",
    "\n",
    "<p>返回矩阵中的所有单元格的坐标，并按与<em>&nbsp;</em><code>(rCenter, cCenter)</code><em>&nbsp;</em>的 <strong>距离</strong> 从最小到最大的顺序排。你可以按 <strong>任何</strong> 满足此条件的顺序返回答案。</p>\n",
    "\n",
    "<p>单元格<code>(r1, c1)</code> 和 <code>(r2, c2)</code> 之间的距离为<code>|r1 - r2| + |c1 - c2|</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rows = 1, cols = 2, rCenter = 0, cCenter = 0\n",
    "<strong>输出：</strong>[[0,0],[0,1]]\n",
    "<strong>解释</strong>：从 (r0, c0) 到其他单元格的距离为：[0,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rows = 2, cols = 2, rCenter = 0, cCenter = 1\n",
    "<strong>输出：</strong>[[0,1],[0,0],[1,1],[1,0]]\n",
    "<strong>解释</strong>：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2]\n",
    "[[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>rows = 2, cols = 3, rCenter = 1, cCenter = 2\n",
    "<strong>输出：</strong>[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]\n",
    "<strong>解释</strong>：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3]\n",
    "其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= rows, cols &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= rCenter &lt; rows</code></li>\n",
    "\t<li><code>0 &lt;= cCenter &lt; cols</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [matrix-cells-in-distance-order](https://leetcode.cn/problems/matrix-cells-in-distance-order/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [matrix-cells-in-distance-order](https://leetcode.cn/problems/matrix-cells-in-distance-order/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['1\\n2\\n0\\n0', '2\\n2\\n0\\n1', '2\\n3\\n1\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        max_d = max(rCenter, rows-1-rCenter)+max(cCenter, cols-1-cCenter)\n",
    "        ans = []\n",
    "        for d in range(max_d+1):\n",
    "            for dx in range(d+1):\n",
    "                dy = d-dx\n",
    "                if dx == 0:\n",
    "                    xs = [dx]\n",
    "                else:\n",
    "                    xs = [dx,-dx]\n",
    "                if dy == 0:\n",
    "                    ys = [dy]\n",
    "                else:\n",
    "                    ys = [dy,-dy]\n",
    "                for ddx in xs:\n",
    "                    for ddy in ys:\n",
    "                        nx = rCenter+ddx\n",
    "                        ny = cCenter+ddy\n",
    "                        if 0<=nx<rows and 0<=ny<cols:\n",
    "                            ans.append((nx, ny))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        ret=[(i,j) for i in range(rows) for j in range(cols)]\n",
    "        ret.sort(key=lambda x:abs(x[0]-rCenter)+abs(x[1]-cCenter))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        res = [(i,j)for i in range(rows) for j in range(cols)]\n",
    "        res.sort(key=lambda x:abs(x[0]-rCenter)+abs(x[1]-cCenter))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        ret = [(i, j) for i in range(rows) for j in range(cols)]\n",
    "        ret.sort(key=lambda x: abs(x[0] - rCenter) + abs(x[1] - cCenter))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        res=[(i,j) for i in range(rows) for j in range(cols)]\n",
    "        res.sort(key=lambda lst:abs(lst[0]-rCenter)+abs(lst[1]-cCenter))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        res = [(i,j) for i in range(rows) for j in range(cols)]\n",
    "        res.sort(key=lambda x:abs(x[0]-rCenter)+abs(x[1]-cCenter))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # nums = []\n",
    "        # for i in range(rows):\n",
    "        #     for j in range(cols):\n",
    "        #         t =abs(i-rCenter)+abs(j-cCenter)\n",
    "        #         nums.append((t,i,j))\n",
    "        # nums.sort()\n",
    "        # ans = []\n",
    "        # for w,x,y in nums:\n",
    "        #     ans.append([x,y])\n",
    "        # return ans\n",
    "\n",
    "        ret = [(i, j) for i in range(rows) for j in range(cols)]\n",
    "        ret.sort(key=lambda x: abs(x[0] - rCenter) + abs(x[1] - cCenter))\n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        ret = [(i, j) for i in range(rows) for j in range(cols)]\n",
    "        ret.sort(key=lambda x: abs(x[0] - rCenter) + abs(x[1] - cCenter))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # 经典广搜\n",
    "        ans = [[rCenter, cCenter]]\n",
    "        m = [[True] * cols for _ in range(rows)]\n",
    "        m[rCenter][cCenter] = False\n",
    "        cur = 0\n",
    "        \n",
    "        total = rows * cols\n",
    "        while cur < total:\n",
    "            r, c = ans[cur]\n",
    "            cur += 1\n",
    "            for r2, c2 in (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1):\n",
    "                if -1<r2<rows and -1<c2<cols and m[r2][c2]:\n",
    "                    m[r2][c2] = False\n",
    "                    ans.append((r2, c2))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        ret = [*product(range(rows), range(cols))]\n",
    "        ret.sort(key=lambda x: abs(x[0] - rCenter) + abs(x[1] - cCenter))\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        output = []\n",
    "        def check_in_matrix(x, y, outputlist):\n",
    "            if x>=0 and x< rows and y >=0 and y < cols:\n",
    "                if [x, y] not in outputlist:\n",
    "                    return True\n",
    "            else:\n",
    "                return False\n",
    "                \n",
    "        for d in range(rows+cols):\n",
    "            for i in range(d+1):\n",
    "\n",
    "                if check_in_matrix(rCenter+i, cCenter+d-i, output):\n",
    "                    output.append([rCenter+i, cCenter+d-i])\n",
    "\n",
    "                if check_in_matrix(rCenter+i, cCenter-d+i, output):\n",
    "                    output.append([rCenter+i, cCenter-d+i])\n",
    "                    \n",
    "                if check_in_matrix(rCenter-i, cCenter+d-i, output):\n",
    "                    output.append([rCenter-i, cCenter+d-i])\n",
    "\n",
    "                if check_in_matrix(rCenter-i, cCenter-d+i, output):\n",
    "                    output.append([rCenter-i, cCenter-d+i])\n",
    "                \n",
    "            \n",
    "        return output\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        ret = [(i, j) for i in range(rows) for j in range(cols)]\n",
    "        ret.sort(key=lambda x: abs(x[0] - rCenter) + abs(x[1] - cCenter))\n",
    "        return ret\n",
    "\n",
    "\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        n = rows * cols\n",
    "        start = (rCenter,cCenter)\n",
    "        found = [start]\n",
    "        i = 0\n",
    "        \n",
    "        while len(found) != n:\n",
    "            cur = found[i]\n",
    "            r = cur[0]\n",
    "            c = cur[1]\n",
    "            if r + 1 < rows and (r+1,c) not in found:\n",
    "                found.append((r+1,c))\n",
    "            if r - 1 >= 0 and (r-1,c) not in found:\n",
    "                found.append((r-1,c))\n",
    "            if c + 1 < cols and (r,c+1) not in found:\n",
    "                found.append((r,c+1))\n",
    "            if c - 1 >= 0 and (r,c-1) not in found:\n",
    "                found.append((r,c-1))\n",
    "            i += 1\n",
    "        return found\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        ret = [(i, j) for i in range(rows) for j in range(cols)]\n",
    "        ret.sort(key=lambda x: abs(x[0] - rCenter) + abs(x[1] - cCenter))\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        a=[]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                a.append([i,j])\n",
    "        a.sort(key=lambda x:abs(x[0]-rCenter)+abs(x[1]-cCenter))\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        dirs = [(1, 1), (1, -1), (-1, -1), (-1, 1)]\n",
    "        maxDist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter)\n",
    "        row, col = rCenter, cCenter\n",
    "        ret = [[row, col]]\n",
    "        for dist in range(1, maxDist + 1):\n",
    "            row -= 1\n",
    "            for i, (dr, dc) in enumerate(dirs):\n",
    "                while (i % 2 == 0 and row != rCenter) or (i % 2 != 0 and col != cCenter):\n",
    "                    if 0 <= row < rows and 0 <= col < cols:\n",
    "                        ret.append([row, col])\n",
    "                    row += dr\n",
    "                    col += dc\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        buckets = [[] for _ in range(rows+cols)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                distance = abs(i-rCenter) + abs(j-cCenter)\n",
    "                buckets[distance].append([i,j])\n",
    "        \n",
    "        res = []\n",
    "        for bucket in buckets:\n",
    "            res.extend(bucket)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # 经典广搜\n",
    "        ans = [[rCenter, cCenter]]\n",
    "        not_seen = {*product(range(rows), range(cols))}\n",
    "        not_seen.remove((rCenter, cCenter))\n",
    "        cur = 0\n",
    "        while cur < rows * cols:\n",
    "            r, c = ans[cur]\n",
    "            cur += 1\n",
    "            for p in (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1):\n",
    "                if p in not_seen:\n",
    "                    not_seen.remove(p)\n",
    "                    ans.append(p)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        dirs = [(1, 1), (1, -1), (-1, -1), (-1, 1)]\n",
    "        maxDist = max(rCenter, rows - 1 - rCenter) + max(cCenter, cols - 1 - cCenter)\n",
    "        row, col = rCenter, cCenter\n",
    "        ret = [[row, col]]\n",
    "        for dist in range(1, maxDist + 1):\n",
    "            row -= 1\n",
    "            for i, (dr, dc) in enumerate(dirs):\n",
    "                while (i % 2 == 0 and row != rCenter) or (i % 2 != 0 and col != cCenter):\n",
    "                    if 0 <= row < rows and 0 <= col < cols:\n",
    "                        ret.append([row, col])\n",
    "                    row += dr\n",
    "                    col += dc\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        result=[[rCenter,cCenter]]\n",
    "        max_dis=max(rCenter+cCenter,rows-1-rCenter+cCenter,rCenter+cols-1-cCenter,rows+cols-2-rCenter-cCenter)\n",
    "        for dis in range(1,max_dis+1):\n",
    "            for x_dis in range(0,dis+1):\n",
    "                y_dis=dis-x_dis\n",
    "                if rCenter-y_dis>=0:\n",
    "                    if cCenter-x_dis>=0:\n",
    "                        result.append([rCenter-y_dis,cCenter-x_dis])\n",
    "                    if x_dis>0 and cCenter+x_dis<cols:\n",
    "                        result.append([rCenter-y_dis,cCenter+x_dis])\n",
    "                if y_dis>0 and rCenter+y_dis<rows:         \n",
    "                    if cCenter-x_dis>=0:\n",
    "                        result.append([rCenter+y_dis,cCenter-x_dis])\n",
    "                    if x_dis>0 and cCenter+x_dis<cols:\n",
    "                        result.append([rCenter+y_dis,cCenter+x_dis])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, R, C, r0, c0):\n",
    "        dist_list = [[] for i in range(R + C)]\n",
    "        for i in range(R):\n",
    "            for j in range(C):\n",
    "                dist_list[abs(r0-i) + abs(c0-j)].append([i, j])\n",
    "        result = []\n",
    "        for i in dist_list:\n",
    "            if i:\n",
    "                result.extend(i)\n",
    "            else:\n",
    "                break\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        ans = [[r,c] for r in range(rows) for c in range(cols)]\n",
    "        ans.sort(key = lambda x:abs(x[0]-rCenter) + abs(x[1]-cCenter))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # 建桶\n",
    "        buckets = [[] for _ in range(rows+cols)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                distance = abs(i-rCenter) + abs(j-cCenter)\n",
    "                buckets[distance].append([i,j])\n",
    "\n",
    "        result = []\n",
    "        for bucket in buckets:\n",
    "            if bucket:\n",
    "                result.extend(bucket)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # 经典广搜\n",
    "        ans = [[rCenter, cCenter]]\n",
    "        not_seen = {*product(range(rows), range(cols))}\n",
    "        not_seen.remove((rCenter, cCenter))\n",
    "        q = deque(ans)\n",
    "        while q:\n",
    "            r, c = q.popleft()\n",
    "            for p in (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1):\n",
    "                if p in not_seen:\n",
    "                    not_seen.remove(p)\n",
    "                    ans.append(p)\n",
    "                    q.append(p)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        buckets = [[] for _ in range(rows+cols)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                distance = abs(i-rCenter) + abs(j-cCenter)\n",
    "                buckets[distance].append([i,j])\n",
    "\n",
    "        res = []\n",
    "        for bucket in buckets:\n",
    "            res.extend(bucket)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        matrices = [[row, col] for row in range(rows) for col in range(cols)]\n",
    "        res = sorted(matrices, key=lambda x: (abs(x[0] - rCenter) + abs(x[1] - cCenter)))\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        res_value = [[] for i in range(rows+cols)] \n",
    "        for x in range(rows):\n",
    "            for y in range(cols):\n",
    "                res_value[abs(x - rCenter) + abs(y - cCenter)].append([x,y])\n",
    "        result = []\n",
    "        for l in res_value:\n",
    "            result += l\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        return sorted([[r, c] for r, c in product(range(rows), range(cols))], key=lambda cell: abs(cell[0]-rCenter) + abs(cell[1]-cCenter))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        return sorted([[r, c] for r, c in product(range(rows), range(cols))], key=(lambda cell: abs(cell[0]-rCenter) + abs(cell[1]-cCenter)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        dist_list = [[] for _ in range(max(rCenter, rows-rCenter)+max(cCenter, cols-cCenter)+1)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                distinct = abs(rCenter-i) + abs(cCenter-j)\n",
    "                dist_list[distinct].append([i,j])\n",
    "        return sum(dist_list,[])\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        hashs=dict()\n",
    "        maxlength=max(rows-rCenter,rCenter)+max(cols-cCenter,cCenter)\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                lij=abs(i-rCenter)+abs(j-cCenter)\n",
    "                if lij in hashs:\n",
    "                    hashs[lij].append([i,j])\n",
    "                else:\n",
    "                    hashs[lij]=[[i,j]]\n",
    "        ans=[]\n",
    "        for key,value in sorted(hashs.items()):\n",
    "            for v in value:\n",
    "                ans.append(v)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        result = [[0]*2 for _ in range(rows*cols)]\n",
    "        print(result)\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                result[i*cols+j][0] = i\n",
    "                result[i*cols+j][1] = j\n",
    "       \n",
    "        result = sorted(result, key=lambda x: (abs(x[0]-rCenter) + abs(x[1]-cCenter)))\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        alist = []\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                alist.append([i,j,abs(i-rCenter)+abs(j-cCenter)])\n",
    "        alist.sort(key = lambda x : x[2])\n",
    "        for i in range(rows*cols):\n",
    "            alist[i] = [alist[i][0]] + [alist[i][1]]\n",
    "        return alist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        ans, lst = [], []\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                lst.append((abs(r - rCenter) + abs(c - cCenter), (r, c)))\n",
    "        lst.sort()\n",
    "        for d, pos in lst:\n",
    "            ans.append(pos)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        dist_list = [[] for _ in range(max(rCenter, rows-rCenter)+max(cCenter, cols-cCenter)+1)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                distinct = abs(rCenter-i) + abs(cCenter-j)\n",
    "                dist_list[distinct].append([i,j])\n",
    "        result = []\n",
    "        return sum(dist_list,[])\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        def takeThird(elem):\n",
    "            return elem[2]\n",
    "        ans=[]\n",
    "        for i in range(0,rows):\n",
    "            for j in range(0,cols):\n",
    "                ans.append([i,j,(abs(i-rCenter)+abs(j-cCenter))])\n",
    "        ans.sort(key=takeThird)\n",
    "        for i in range(0,len(ans)):\n",
    "            del ans[i][2]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self,rows,cols,rCenter,cCenter):\n",
    "    \n",
    "        kv = list()\n",
    "        rList = list()\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                k = abs(rCenter-i)+abs(cCenter-j)\n",
    "                kv.append([i, j, k])\n",
    "    \n",
    "        kv.sort(key=lambda x:x[2])\n",
    "        for m in range(len(kv)):\n",
    "            app = kv[m]\n",
    "            rList.append(app[0:2])\n",
    "        return rList"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        ans = [[x, y] for x in range(rows) for y in range(cols)]\n",
    "        l = []\n",
    "        for x, y in ans:\n",
    "            d = abs(x-rCenter) + abs(y-cCenter)\n",
    "            l.append((d, [x, y]))\n",
    "        l.sort()\n",
    "        return [tup[1] for tup in l]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        dic = defaultdict(list)\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                tmp = abs(rCenter - i) + abs(cCenter - j)\n",
    "                dic[tmp].append([i, j])\n",
    "        print(dic)\n",
    "        res = []\n",
    "        for key, val in sorted(dic.items(), key=lambda x: (x[0])):\n",
    "            res.extend(val)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from operator import itemgetter\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        indexAndDis = []\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                dis = abs(i - rCenter) + abs(j - cCenter)\n",
    "                indexAndDis.append([i,j,dis])\n",
    "        indexAndDis = sorted(indexAndDis, key = itemgetter(2))\n",
    "        n = len(indexAndDis)\n",
    "        for i in range(n):\n",
    "            del indexAndDis[i][2]\n",
    "        return indexAndDis\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def distance(self, r1, c1, r2, c2):\n",
    "        return abs(r1 - r2) + abs(c1 - c2)\n",
    "\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        distances = []\n",
    "        for r in range(rows):\n",
    "            for c in range(cols):\n",
    "                dist = self.distance(r, c, rCenter, cCenter)\n",
    "                distances.append((dist, r, c))\n",
    "\n",
    "        distances.sort()  # 按距离从小到大排序\n",
    "\n",
    "        # 提取排序后的结果中的坐标并返回\n",
    "        result = [(r, c) for dist, r, c in distances]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        \"\"\"\n",
    "        1. 计算出坐标相应的距离，\n",
    "        2. 按距离排序，\n",
    "        3. 返回\n",
    "        \"\"\"\n",
    "        t = [([r,c],abs(r-rCenter)+abs(c-cCenter)) for r in range(rows) for c in range(cols)]\n",
    "        t.sort(key=lambda x: x[1])\n",
    "        return [[r,c] for ([r,c],_) in t]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        matrix = []\n",
    "        for i in range(0,rows,1):\n",
    "            for j in range(0,cols,1):\n",
    "                matrix.append([i,j])\n",
    "        distance=[]\n",
    "        for i in matrix:\n",
    "            dis = abs(rCenter - i[0]) + abs(cCenter - i[1])\n",
    "            distance.append(dis)\n",
    "        zip_d_m = zip(distance,matrix)\n",
    "        sorted_zip_d_m = sorted(zip_d_m, key= lambda x:x[0])\n",
    "        sorted_distance,sorted_matrix = zip(*sorted_zip_d_m)\n",
    "        return sorted_matrix\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        d = {}\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                d[(i,j)] = abs(i - rCenter) + abs(j - cCenter)\n",
    "\n",
    "        d = sorted(d.items(), key=lambda x: x[1])\n",
    "        return [[k[0],k[1]] for k,v in d]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        distances = []\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                distance = abs(i-rCenter)+abs(j-cCenter)\n",
    "                distances.append((i,j,distance))\n",
    "    \n",
    "        distances.sort(key=lambda x:x[2])\n",
    "        return [(x,y) for x,y,_ in distances]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        li=[]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                li.append(     ([i,j],abs(i-rCenter)+abs(j-cCenter))   )\n",
    "        ret=sorted(li,key=lambda x:x[1])\n",
    "        return [x[0] for x in ret]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, x: int, y: int) -> List[List[int]]:\n",
    "        table = {}\n",
    "        ans = []\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                ans.append([i,j])\n",
    "                table[i*cols+j] = abs(i-x)+abs(j-y)\n",
    "        #print(table)\n",
    "        ans.sort(key=lambda x:table[x[0]*cols+x[1]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # 深度优先或广度优先遍历，用哈希表存每个点的距离，然后进行排序即可\n",
    "        # -------------------------DFS 栈------------------------------\n",
    "        visited = [[False] * cols for _ in range(rows)]\n",
    "        stack = [(rCenter, cCenter)]\n",
    "        visited[rCenter][cCenter] = True\n",
    "        # 第一个元素（元组）表示坐标，第二个元素表示该坐标与参考点的距离\n",
    "        tmp = []\n",
    "        dir_rows = [-1, 0, 1, 0]\n",
    "        dir_cols = [0, 1, 0, -1]\n",
    "        while stack:\n",
    "            point = stack.pop()\n",
    "            # visited[point[0]][point[1]] = True\n",
    "            tmp.append(((point[0], point[1]), abs(point[0] - rCenter) + abs(point[1] - cCenter)))\n",
    "            for i in range(4):\n",
    "                tmp_x = point[0] + dir_rows[i]\n",
    "                tmp_y = point[1] + dir_cols[i]\n",
    "                if 0 <= tmp_x < rows and 0 <= tmp_y < cols and not visited[tmp_x][tmp_y]:\n",
    "                    stack.append((tmp_x, tmp_y))\n",
    "                    visited[tmp_x][tmp_y] = True\n",
    "\n",
    "        res = sorted(tmp, key=lambda x:x[1])\n",
    "        return list(map(lambda x:x[0], res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\r\n",
    "        # 计算所有单元格与(rCenter, cCenter)的距离，并按距离从小到大排序\r\n",
    "        distances = []\r\n",
    "        for i in range(rows):\r\n",
    "            for j in range(cols):\r\n",
    "                dist = abs(i - rCenter) + abs(j - cCenter)\r\n",
    "                distances.append((i, j, dist))\r\n",
    "        distances.sort(key=lambda x: x[2])\r\n",
    "        # 将所有单元格按距离从小到大依次加入结果列表中\r\n",
    "        result = [[x[0], x[1]] for x in distances]\r\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # 经典广搜\n",
    "        ans = [[rCenter, cCenter]]\n",
    "        seen = {(rCenter, cCenter)}\n",
    "        cur = 0\n",
    "        \n",
    "        total = rows * cols\n",
    "        while cur < total:\n",
    "            r, c = ans[cur]\n",
    "            cur += 1\n",
    "            for r2, c2 in (r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1):\n",
    "                if -1<r2<rows and -1<c2<cols and (r2, c2) not in seen:\n",
    "                    seen.add((r2, c2))\n",
    "                    ans.append((r2, c2))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        nums = []\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                t =abs(i-rCenter)+abs(j-cCenter)\n",
    "                nums.append((t,i,j))\n",
    "        nums.sort()\n",
    "        ans = []\n",
    "        for w,x,y in nums:\n",
    "            ans.append([x,y])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        result=[]\n",
    "        step=0\n",
    "        while True:\n",
    "            stepresult=[]\n",
    "            for r in range(step+1):\n",
    "                c=step-r\n",
    "                if rCenter+r<=rows-1 and cCenter+c<=cols-1:\n",
    "                    stepresult.append((rCenter+r,cCenter+c))\n",
    "                if rCenter+r<=rows-1 and cCenter-c>=0:\n",
    "                    stepresult.append((rCenter+r,cCenter-c))\n",
    "                if rCenter-r>=0 and cCenter+c<=cols-1:\n",
    "                    stepresult.append((rCenter-r,cCenter+c))\n",
    "                if rCenter-r>=0 and cCenter-c>=0:\n",
    "                    stepresult.append((rCenter-r,cCenter-c))\n",
    "            step+=1\n",
    "            if stepresult==[]:\n",
    "                break\n",
    "            else:\n",
    "                result.extend(list(set(stepresult)))\n",
    "        return [list(i) for i in result]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        res_dic = {}\n",
    "        mid_list = []\n",
    "        res_list = []\n",
    "        i = j = 0\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                res_dic[i,j] = abs(i-rCenter) + abs(j-cCenter)\n",
    "        mid_list = sorted(res_dic.items(),key = lambda x: x[1])\n",
    "        for idx in range(len(mid_list)):\n",
    "            res_list.append(mid_list[idx][0])\n",
    "        return res_list\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        dis = {}\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "               dis[(i, j)] = abs(i - rCenter) + abs(j - cCenter)\n",
    "        return [ i[0] for i in sorted(dis.items(), key = lambda dis : dis[1])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        dic = {}\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                dic[(i,j)] = abs(i-rCenter)+abs(j-cCenter)\n",
    "        l = sorted(dic.items(), key = lambda x:x[1])\n",
    "        x = []\n",
    "        for i in l:\n",
    "            x.append(i[0])\n",
    "        return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        d = {}\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                dis = abs(i - rCenter) + abs(j - cCenter)\n",
    "                d[(i, j)] = dis\n",
    "        \n",
    "        #print(d)\n",
    "        L = sorted(d, key = lambda x: d[x])\n",
    "        return ([list(x) for x in L ])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        r_list = []\n",
    "        res_list = []\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                r_list.append([(abs(rCenter-i) + abs(cCenter-j)), [i, j]])\n",
    "\n",
    "        print(r_list)\n",
    "        r_list.sort(key=lambda x: x[0])\n",
    "        print(r_list)\n",
    "\n",
    "        for x, y in r_list:\n",
    "            res_list.append(y)\n",
    "        return res_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        distance_list = [[] for _ in range(rows*cols)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                cur_distance = abs(i - rCenter) + abs(j - cCenter)\n",
    "                distance_list[cur_distance].append([i, j])\n",
    "        rs = []\n",
    "        for k in distance_list:\n",
    "            if k:\n",
    "                rs.extend(k)\n",
    "            else: \n",
    "                break\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # 建桶\n",
    "        buckets = [[] for _ in range(rows*cols)]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                distance = abs(i-rCenter) + abs(j-cCenter)\n",
    "                buckets[distance].append([i,j])\n",
    "        result = []\n",
    "        for bucket in buckets:\n",
    "            if bucket:\n",
    "                result.extend(bucket)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        q = deque([(rCenter, cCenter)])\n",
    "        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]\n",
    "        mp_set = set()\n",
    "        ans = []\n",
    "\n",
    "        while q:\n",
    "            r, c = q.popleft()\n",
    "            ans.append([r, c])\n",
    "            mp_set.add((r, c))\n",
    "\n",
    "            for x, y in dirs:\n",
    "                if 0 <= r + y < rows and 0 <= c + x < cols and (r + y, c + x) not in mp_set:\n",
    "                    q.append((r + y, c + x))\n",
    "                    mp_set.add((r + y, c + x))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        matrices = []\n",
    "        for row in range(rows):\n",
    "            for col in range(cols):\n",
    "                item = [row]\n",
    "                item.append(col)\n",
    "                matrices.append(item)\n",
    "        res = sorted(matrices, key=lambda x: (abs(x[0] - rCenter) + abs(x[1] - cCenter)))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # bfs?\n",
    "        res = []\n",
    "        q = deque([[rCenter, cCenter]])\n",
    "        seen = set()\n",
    "        seen.add(rCenter*101 + cCenter)\n",
    "        moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n",
    "        def check(r, c):\n",
    "            hashcode = r*101+c\n",
    "            if hashcode in seen:\n",
    "                return False\n",
    "            seen.add(hashcode)\n",
    "            return True\n",
    "        \n",
    "        def move(r, c):\n",
    "            if r<0 or r>=rows or c<0 or c >= cols or not check(r, c):\n",
    "                return\n",
    "            q.append([r, c])\n",
    "\n",
    "        while q:\n",
    "            pos = q.popleft()\n",
    "            res.append(pos)\n",
    "            for mr, mc in moves:\n",
    "                move(pos[0] + mr, pos[1] + mc)\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n",
    "        # bucket sort\n",
    "        # maxDist = max(rCenter, rows-1-rCenter) + max(cCenter, cols-1-cCenter)\n",
    "        # bucket = collections.defaultdict(list)\n",
    "        # dist = lambda r1, c1, r2, c2: abs(r1-r2) + abs(c1-c2)\n",
    "\n",
    "        # for i in range(rows):\n",
    "        #     for j in range(cols):\n",
    "        #         bucket[dist(i, j, rCenter, cCenter)].append([i,j])\n",
    "        \n",
    "        # res = []\n",
    "        # for i in range(maxDist+1):\n",
    "        #     res.extend(bucket[i])\n",
    "        \n",
    "        # return res\n",
    "\n",
    "        # row, col = rCenter, cCenter\n",
    "        # q = deque([[rCenter, cCenter]])\n",
    "        # res = [[rCenter, cCenter]]\n",
    "        # move = [[1, 1], [1, -1], [-1, -1], [-1, 1]]\n",
    "        # for dist in range(1, maxDist+1):\n",
    "        #     row -= 1\n",
    "        #     for i, (dr, dc) in enumerate(move):\n",
    "        #         while (i%2 == 0 and row != rCenter) or (i%2 == 0 and col != cCenter):\n",
    "        #             if 0 <= row <= rows and 0<=col<=cols:\n",
    "        #                 res.append([row, col])\n",
    "        #             row += dr\n",
    "        #             col += dc\n",
    "        # return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        result=[]\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                result.append([i,j])\n",
    "        l=len(result)\n",
    "        dic={}\n",
    "        for i in range(l):\n",
    "            val=abs(result[i][0]-rCenter)+abs(result[i][1]-cCenter)\n",
    "            if val not in dic:\n",
    "                dic[val]=result[i]\n",
    "            else:\n",
    "                first=dic[val]\n",
    "                for j in range(2):\n",
    "                    first.append(result[i][j])\n",
    "        #dic_order=sorted(dic.items(),key=lambda x:x[1])\n",
    "        final=[]\n",
    "        for i in sorted(dic.keys()):\n",
    "            l=len(dic[i])\n",
    "            for j in range(0,l,2):\n",
    "                final=final+[[dic[i][j],dic[i][j+1]]]\n",
    "        return final\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, R: int, C: int, r0: int, c0: int) -> List[List[int]]:\n",
    "        distance={}\n",
    "        for i in range(R):\n",
    "            for j in range(C):\n",
    "                x=str(i)+' '+str(j)\n",
    "                distance[x]=abs(i-r0)+abs(j-c0) \n",
    "        distance=sorted(distance.items(), key=lambda item:item[1])\n",
    "        res=[]\n",
    "        for d in distance:\n",
    "            i,j=d[0].split()    \n",
    "            res.append([i,j])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # 深度优先或广度优先遍历，用哈希表存每个点的距离，然后进行排序即可\n",
    "        # -------------------------DFS 栈------------------------------\n",
    "        visited = [[False] * cols for _ in range(rows)]\n",
    "        stack = [(rCenter, cCenter)]\n",
    "        visited[rCenter][cCenter] = True\n",
    "        # 第一个元素（元组）表示坐标，第二个元素表示该坐标与参考点的距离\n",
    "        tmp = [((rCenter, cCenter), 0)]\n",
    "        dir_rows = [-1, 0, 1, 0]\n",
    "        dir_cols = [0, 1, 0, -1]\n",
    "        while stack:\n",
    "            point = stack.pop()\n",
    "            # visited[point[0]][point[1]] = True\n",
    "            # tmp.append(((point[0], point[1]), abs(point[0] - rCenter) + abs(point[1] - cCenter)))\n",
    "            for i in range(4):\n",
    "                tmp_x = point[0] + dir_rows[i]\n",
    "                tmp_y = point[1] + dir_cols[i]\n",
    "                if 0 <= tmp_x < rows and 0 <= tmp_y < cols and not visited[tmp_x][tmp_y]:\n",
    "                    stack.append((tmp_x, tmp_y))\n",
    "                    tmp.append(((tmp_x, tmp_y), abs(tmp_x - rCenter) + abs(tmp_y - cCenter)))\n",
    "                    visited[tmp_x][tmp_y] = True\n",
    "\n",
    "        res = sorted(tmp, key=lambda x:x[1])\n",
    "        return list(map(lambda x:x[0], res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        # 广度优先搜索\n",
    "        visited = [[False] * cols for _ in range(rows)]\n",
    "        visited[rCenter][cCenter] = True\n",
    "        d = [(rCenter, cCenter)]\n",
    "        dir_rows = [-1, 0, 1, 0]\n",
    "        dir_cols = [0, 1, 0, -1]\n",
    "        tmp = [((rCenter, cCenter), 0)]\n",
    "        while d:\n",
    "            point = d.pop()\n",
    "            for i in range(4):\n",
    "                tmp_x = point[0] + dir_rows[i]\n",
    "                tmp_y = point[1] + dir_cols[i]\n",
    "                if 0 <= tmp_x < rows and 0 <= tmp_y < cols and not visited[tmp_x][tmp_y]:\n",
    "                    d.insert(0, (tmp_x, tmp_y))\n",
    "                    visited[tmp_x][tmp_y] = True\n",
    "                    tmp.append(([tmp_x, tmp_y], abs(tmp_x - rCenter) + abs(tmp_y - cCenter)))\n",
    "        res = sorted(tmp, key=lambda x:x[1])\n",
    "        return list(map(lambda x:x[0], res))\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # # 深度优先或广度优先遍历，用哈希表存每个点的距离，然后进行排序即可\n",
    "        # # -------------------------DFS 栈------------------------------\n",
    "        # visited = [[False] * cols for _ in range(rows)]\n",
    "        # stack = [(rCenter, cCenter)]\n",
    "        # visited[rCenter][cCenter] = True\n",
    "        # # 第一个元素（元组）表示坐标，第二个元素表示该坐标与参考点的距离\n",
    "        # tmp = [((rCenter, cCenter), 0)]\n",
    "        # dir_rows = [-1, 0, 1, 0]\n",
    "        # dir_cols = [0, 1, 0, -1]\n",
    "        # while stack:\n",
    "        #     point = stack.pop()\n",
    "        #     # visited[point[0]][point[1]] = True\n",
    "        #     # tmp.append(((point[0], point[1]), abs(point[0] - rCenter) + abs(point[1] - cCenter)))\n",
    "        #     for i in range(4):\n",
    "        #         tmp_x = point[0] + dir_rows[i]\n",
    "        #         tmp_y = point[1] + dir_cols[i]\n",
    "        #         if 0 <= tmp_x < rows and 0 <= tmp_y < cols and not visited[tmp_x][tmp_y]:\n",
    "        #             stack.append((tmp_x, tmp_y))\n",
    "        #             tmp.append(((tmp_x, tmp_y), abs(tmp_x - rCenter) + abs(tmp_y - cCenter)))\n",
    "        #             visited[tmp_x][tmp_y] = True\n",
    "\n",
    "        # res = sorted(tmp, key=lambda x:x[1])\n",
    "        # return list(map(lambda x:x[0], res))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        stack, ans, s = [[rCenter,cCenter]], [], set()\n",
    "        s.add((rCenter,cCenter))\n",
    "        while stack:\n",
    "            x, y = stack.pop(0)\n",
    "            ans.append([x,y])\n",
    "            if 0 <= x-1 < rows and (x-1,y) not in s:\n",
    "                stack.append([x-1,y])\n",
    "                s.add((x-1,y))\n",
    "            if 0 <= x+1 <rows and (x+1,y) not in s:\n",
    "                stack.append([x+1,y])\n",
    "                s.add((x+1,y))\n",
    "            if 0 <= y-1 < cols and (x,y-1) not in s:\n",
    "                stack.append([x,y-1])\n",
    "                s.add((x,y-1))\n",
    "            if 0 <= y+1 < cols and (x,y+1) not in s:\n",
    "                stack.append([x,y+1])\n",
    "                s.add((x,y+1))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int):\n",
    "        num = 0\n",
    "        dis = 0\n",
    "        nums1 = 0\n",
    "        nums2 = 0\n",
    "        nums = [rCenter, cCenter]\n",
    "        tmplist = []\n",
    "        distance = []\n",
    "        lastlist = []\n",
    "        endlist = []\n",
    "        for i in range(cols):\n",
    "            for j in range(rows):\n",
    "                tmplist.append([j,i])\n",
    "        print(tmplist)\n",
    "        for i in range(len(tmplist)):\n",
    "            num1 = abs(nums[0] - tmplist[i][0])\n",
    "            num2 = abs(nums[1] - tmplist[i][1])\n",
    "            lastlist.append([num1,num2])\n",
    "        for i in range(len(lastlist)):\n",
    "            num = i\n",
    "            distance.append([sum(lastlist[i]),num])\n",
    "        distance.sort()\n",
    "        for i in range(len(distance)):\n",
    "            endlist.append(tmplist[distance[i][1]])\n",
    "        return endlist"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        distance = {}\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                distance[str([i, j])] = abs(i - rCenter) + abs(j - cCenter)\n",
    "        distance = [k for k, v in sorted(distance.items(), key=lambda x:x[1])]\n",
    "        \n",
    "        return [eval(item) for item in distance]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        DIRS = [[-1, 0], [0, 1], [1, 0], [0, -1]]\n",
    "        res = [[rCenter, cCenter]]\n",
    "        deq = deque([(rCenter, cCenter)])\n",
    "        visited = {(rCenter, cCenter)}\n",
    "        while deq:\n",
    "            x, y = deq.popleft()\n",
    "            for dx, dy in DIRS:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx <= rows-1 and 0 <= ny <= cols-1 and (nx, ny) not in visited:\n",
    "                    res.append([nx, ny])\n",
    "                    visited.add((nx, ny))\n",
    "                    deq.append((nx, ny))\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, n: int, m: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        st = set()\n",
    "        st.add((rCenter, cCenter))\n",
    "        q = [[rCenter, cCenter]]\n",
    "        ans = []\n",
    "        while q:\n",
    "            t, q = q, []\n",
    "            ans += t\n",
    "            for x, y in t:\n",
    "                for dx, dy in ((1, 0), (0, 1), (-1, 0), (0, -1)):\n",
    "                    if 0 <= x + dx < n and 0 <= y + dy < m and (x + dx, y + dy) not in st:\n",
    "                        q.append([x + dx, y + dy])\n",
    "                        st.add((x + dx, y + dy))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        processList = []\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                processList.append([[i,j], abs(i - rCenter) + abs(j - cCenter)])\n",
    "\n",
    "        processList.sort(key = lambda x:(x[1]))\n",
    "        print(processList)\n",
    "\n",
    "        result = [i[0] for i in processList]\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        ans = []\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                ans.append([i,j,abs(i-rCenter) + abs(j-cCenter)])\n",
    "        ans.sort(key=lambda ans:ans[2])\n",
    "        for i in range(len(ans)):\n",
    "            res.append(ans[i][0:2])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        dis = []\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                dis.append([abs(i-rCenter) + abs(j-cCenter), i, j])\n",
    "        \n",
    "        dis.sort()\n",
    "\n",
    "        return [elem[1:] for elem in dis]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, m: int, n: int, r: int, c: int) -> List[List[int]]:\n",
    "\n",
    "        visit = {(r, c)}\n",
    "        ans = []\n",
    "        stack = deque([[r, c]])\n",
    "        while stack:\n",
    "            x, y = stack.popleft()\n",
    "            ans.append([x, y])\n",
    "            for i, j in [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]:\n",
    "                if 0<=i<m and 0<=j<n and (i, j) not in visit:\n",
    "                    stack.append([i, j])\n",
    "                    visit.add((i, j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        ans = []\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                ans.append([i,j,abs(i-rCenter) + abs(j-cCenter)])\n",
    "        ans.sort(key=lambda ans:ans[2])\n",
    "        for i in range(len(ans)):\n",
    "            res.append(ans[i][0:2])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:\n",
    "        res = []\n",
    "        # 坐标系：[横坐标，纵坐标，距目标点距离]\n",
    "        coordinateSystem = [[[r, c], 0]\n",
    "                            for c in range(cols) for r in range(rows)]\n",
    "        for i in range(rows*cols):\n",
    "            distance = abs(cCenter-coordinateSystem[i][0][1])+abs(rCenter-coordinateSystem[i][0][0])\n",
    "            coordinateSystem[i][1] = distance\n",
    "        coordinateSystem.sort(key=lambda x: (x[1], x[0][0]))\n",
    "\n",
    "        for point in coordinateSystem:\n",
    "            res.append(point[0])\n",
    "\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
